package com.lisp.algorithm.test.sort;

public class IterateBinaryTree {
	
	public static void iterate(Node root) {
		Node first = getFirst(root);
		System.out.println(first.key);
		
		Node next = getNext(first);
		while(next != null) {
			System.out.println(next.key);
			next = getNext(next);
		}
	}
	
	private static Node getFirst(Node n) {
		if(n != null) {
			return leftMost(n);
		} else {
			return null;
		}
	}
	

	private static Node getNext(Node n) {
		// 尝试前进
		// n.left必定为null或已经访问过
		if(n.right != null) {
			return leftMost(n.right);
		}
        
		// 从左侧回退到parent 
		if(n != null && n.parent.left == n) {
			return n.parent;
		}
		
		// 从右侧回退
		while(n.parent != null && n.parent.right == n) {
			n = n.parent;
		}
		return n.parent;
	}
	
	private static Node leftMost(Node subTree) {
		Node n = subTree;
		while(n.left != null) {
			n = n.left;
		}
		return n;
	}
}
